/*
 * @lc app=leetcode.cn id=493 lang=cpp
 *
 * [493] 翻转对
 */

// @lc code=start
class Solution {
private:
    vector<int> temp;
    int count = 0;

    void merge(vector<int>& nums, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        int end = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (end <= hi && (long)temp[i] > (long)temp[end] * 2) {
                end++;
            }
            count += end - mid - 1;
        }

        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }

    void sort(vector<int>& nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        temp.resize(n, 0);
        sort(nums, 0, n - 1);
        return count;
    }
};
// @lc code=end

